/*
 * name: Mabel Xu
 * date: October 10, 2007
 * filename: MyLinkedList.java
 * description: class that acts as a MyLinkedList object ... has appropriate methods for manipulating the MyLinkedList
 */

public class MyLinkedList	// my own class that uses ListNodes to create LinkedLists
{
	private ListNode head;	// field keeps track of memory address of head node

	// pre - mothing!
	// post - initializes null, returns nothing
	// description - constructor to initialize new MyLinkedList
	public MyLinkedList()
	{
		head = null;
	}		// end default constructor

	// pre - a MyLinkedList that is already initialized
	// post - returns number of ListNodes in the MyLinkedList
	// description - goes through all linkages in MyLinkedList, counting all the while, until getNext() is null (meaning no more ListNodes in MyLinkedList)
	public int size()
	{
		if (this.isEmpty())	// if list is empty, then its just zero
			return 0;
		else	// if list is not empty, then count everything
		{
			ListNode temp = head;
			int count = 1;
			while (temp.getNext() != null)	// loop through MyLinkedList and count
			{
				count++;
				temp = temp.getNext();
			}		// end of loop to go through MyLinkedList
			return count;
		}		// end of if list not empty
	}		// end of size() method

	// pre - list initialized
	// post - returns true or false depening on empty or not
	// description - returns true if MyLinkedList is empty, returns false if not empty
	public boolean isEmpty()
	{
		return (head == null? true : false);
	}		// end of isEmpty() method

	// pre - list initiated
	// post - adds new ListNode at specified place, returns true or false depending on success
	// description - private method used to run all "add" methods ... tries to add object to indicated "index" (no nead to return false for empty list since adding element to empty list is viable)
	private boolean add(int i, Object obj)
	{
		if (i < 0 || i > this.size())	// returns false if index given is invalid
			return false;	// makes program skip all the rest ... those code not necessary if index invalid

		// so by now index should be a valid index ...
		if (this.isEmpty())		// if empty, then just make the head the added one
			head = new ListNode(obj, null);
		else if (i == 0)	// if added to head, then just use this way instead ... head has no "previous"
			head = new ListNode(obj, head);
		else	// if added to any other place (including at end) ... then use this way
		{
			ListNode before = head;
			for(int a = 0; a < i - 1; a++)	// advance the "before marker" to the one before the place to add
				before = before.getNext();
			ListNode after = before.getNext();	// this is the one currently at indicated index
			before.setNext(new ListNode(obj, after));	// insert the provided object in between "before" and "after"
		}		// end of "way to add ListNode to any place other than index 0"
		return true;	// if it runs till here, then it added properly ...
	}		// end of "generic add method" that I made myself to add to anyplace I want

	// pre - list initialized
	// post - adds ListNode to end (can be changed by calling different add method) of the LinkedList
	// description - method that calls other method ... to be used as "default add" method
	public boolean add(Object obj)
	{
		return addLast(obj);
	}		// end "default add" method

	// pre - list initialized
	// post - adds ListNode to beginning of the LinkedList
	// description - method that adds to end of LinkedList using the private add method
	public boolean addFirst(Object obj)
	{
		return add(0, obj);
	}		// end of addFirst methiod

	// pre - list initialized
	// post - adds ListNode to end of LinkedList
	// description - method that adds to beginning of LinkedList using private add method
	public boolean addLast(Object obj)
	{
		return add(this.size(), obj);
	}		// end of addLast method

	// pre - list initialized
	// post - returns null if empty list / invalid index, returns old object if set correctly
	// description - sets object at specified "index" to provided object, checking for invalid index
	public Object set(int i, Object obj)
	{
		if (this.isEmpty())		// in case user gives empty list
			return null;
		else if (i >= this.size())	// in case user gives bad input
			return null;
		else	// in case user gives valid input
		{
			ListNode temp = head;
			for(int a = 0; a < i; a++)	// keep looping until get to one to set
				temp = temp.getNext();
			Object old = temp.getValue();
			temp.setValue(obj);
			return old;
		}		// end of actual set method (portion that actually does the setting)
	}		// end of set method

	// pre - list initialized
	// post - returns null if list empty, otherwise returns first value
	// description - checks for empty list, then returns first value
	public Object getFirst()
	{
		if (this.isEmpty())
			return null;
		else
			return head.getValue();
	}		// end of getFirst() method

	// pre - list initialized
	// post - returns null if list empty, otherwise returns last value
	// description - checks for empty list, then returns last value
	public Object getLast()
	{
		if (this.isEmpty())
			return null;
		else	// in case list not empty
		{
			ListNode temp = head;
			while(temp.getNext() != null)	// keep going until get to end of MyLinkedList
				temp = temp.getNext();
			return temp.getValue();
		}		// end of in case list not empty
	}		// end of getLast() method

	// pre - list initialized
	// post - returns object removed, or null if "error"
	// description - returns null if list empty or index bigger than list size, otherwise moves item at index and returns value of removed item
	public Object remove(int i)
	{
		if (this.isEmpty())		// in case list is empty (aka bad user)
			return null;
		else if (i >= this.size())	// in case index invalid (aka bad user)
			return null;
		else if (i == 0)	// needs special treatment if remove head
		{
			ListNode oldHead = head;
			head = head.getNext();
			oldHead.setNext(null);
			return oldHead.getValue();
		}		// end remove head special case
		else	// remove any element other than head
		{
			ListNode temp = head;
			for(int a = 0; a < i - 1; a++)	// loop until get to item before the one to be removed
				temp = temp.getNext();
			ListNode oldNext = temp.getNext();
			ListNode newNext = temp.getNext().getNext();
			temp.setNext(newNext);
			oldNext.setNext(null);
			return oldNext.getValue();
		}		// end remove element other than head
	}		// end remove() method

	// pre - list initialized
	// post - returns object removed (head element)
	// description - removes the first element in the list by calling remove(0), and returns object removed
	public Object removeFirst()
	{
		return remove(0);
	}		// end removeFirst() method

	// pre - list intialized
	// post - returns object removed (last element)
	// description - removes the last element in the list by calling remove(size() - 1), and returns object removed
	public Object removeLast()
	{
		return remove(this.size() - 1);
	}		// end removeLast() method
	
	// pre - list initialized
	// post - returns string that represents all items in list
	// description - checks of list empty, then returns appropriate string with counter
	public String toString()
	{
		if (this.isEmpty())
			return "cannot print empty list";
		else	// in case list not empty, "buid" the string
		{
			String s = "";
			ListNode temp = head;
			for(int a = 1; temp != null; a++)	// loop through adding each element to string (aka building)
			{
				s += a + " : " + temp.getValue().toString() + "\n";
				temp = temp.getNext();
			}		// end "buildling" the string
			return s;
		}		// end string building (when list not empty)
	}		// end of toString() method
}		// end of MyLinkedList class